package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC376 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 动归中的典型范例
     * @return:
     */
    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length < 2)
                return nums.length;
            int[] up = new int[nums.length];
            int[] down = new int[nums.length];
            up[0] = down[0] = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > nums[i - 1]) {
                    up[i] = down[i - 1] + 1;
                    down[i] = down[i - 1];
                } else if (nums[i] < nums[i - 1]) {
                    down[i] = up[i - 1] + 1;
                    up[i] = up[i - 1];
                } else {
                    down[i] = down[i - 1];
                    up[i] = up[i - 1];
                }
            }
            return Math.max(down[nums.length - 1], up[nums.length - 1]);
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC376 an = new LC376();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
